package algorithm;

import java.util.Arrays;

public class HeapSort {
    public static void upSort(int[] arr){
        int n = arr.length;
        // 堆化
        for (int i = n / 2 - 1; i >= 0; i--)
            maxHeapify(arr, n, i);
        // 堆排序 每次将堆尾与堆顶交换，交换之后数组末尾已经交换的部分就是有序，然后再维护堆 升序使用大项堆 降序使用小堆
        for (int i = n - 1; i > 0; i--){
            swap(arr, 0, i);
            maxHeapify(arr, i, 0);
        }
    }

    public static void downSort(int[] arr){
        int n = arr.length;
        //堆化
        for (int i = n / 2 - 1; i >= 0; i--)
            minHeapify(arr, n, i);
        //排序
        for (int i = n - 1; i > 0; i--){
            swap(arr, 0, i);
            minHeapify(arr, i, 0);
        }
    }

    private static void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }

    //递归调整 i为根的子树满足堆性质
    private static void maxHeapify(int[] arr, int len, int i){
        //root为最大节点索引
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        //比较子树根节点与子结点大小
        if(left < len && arr[i] < arr[left])
            largest = left;
        if(right < len && arr[largest] < arr[right])
            largest = right;

        //最大的节点如果不是父节点
        if(largest != i){
            swap(arr, i, largest);
            //交换后维护所有子树
            maxHeapify(arr, len, largest);
        }
    }

    private static void minHeapify(int[] arr, int len, int i){
        int smallest = i;
        int left = i * 2 + 1;
        int right = i * 2 + 2;
        if(left < len && arr[i] > arr[left])
            smallest = left;
        if(right < len && arr[smallest] > arr[right])
            smallest = right;
        if(i != smallest) {
            swap(arr, i, smallest);
            minHeapify(arr, len, smallest);
        }
    }

    public static void main(String[] args) {
        int[] arr = {1, 20, 12, 13, 15, 9, 0, 2, 8, 6};
        HeapSort.upSort(arr);
        System.out.println(Arrays.toString(arr));
        HeapSort.downSort(arr);
        System.out.println(Arrays.toString(arr));
        System.out.println(Arrays.toString(arr));
    }
}
